package ahaArithmetic;

//炸弹人游戏 广度优先解法
public class Bfs_2 {

    static char[][] map = new char[][]{
            {'#','#','#','#','#','#','#','#','#','#','#','#','#'},
            {'#','G','G','.','G','G','G','#','G','G','G','.','#'},
            {'#','#','#','.','#','G','#','G','#','G','#','G','#'},
            {'#','.','.','.','.','.','.','.','#','.','.','G','#'},
            {'#','G','#','.','#','#','#','.','#','G','#','G','#'},
            {'#','G','G','.','G','G','G','.','#','.','G','G','#'},
            {'#','G','#','.','#','G','#','.','#','.','#','.','#'},
            {'#','#','G','.','.','.','G','.','.','.','.','.','#'},
            {'#','G','#','.','#','G','#','#','#','.','#','G','#'},
            {'#','.','.','.','G','#','G','G','G','.','G','G','#'},
            {'#','G','#','.','#','G','#','G','#','.','#','G','#'},
            {'#','G','G','.','G','G','G','#','G','.','G','G','#'},
            {'#','#','#','#','#','#','#','#','#','#','#','#','#'},
    };
    static Node_2[] nodes = new Node_2[401];
    static int startX = 3;
    static int startY = 3;
    static int x=startX,y=startY;
    static int head = 0;
    static int tail = 1;
    static int max = 0;
    static int next[][] = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};

    public static void main(String[] args) {
        for(int i=0;i<nodes.length;i++){
            nodes[i] = new Node_2();
        }
        nodes[head].x = startX;
        nodes[head].y = startY;
        //nodes[head].n = 1;
        bfs_2();
        System.out.print(max);
    }

    public static void bfs_2(){
        while (head<tail){
            //四个方向走一遍
            for(int i=0;i<=3;i++){
                x = x + next[i][0];
                y = y + next[i][1];
                //判断越界
                if(x<0 || x>12 || y<0 || y>12){
                    x = x - next[i][0];
                    y = y - next[i][1];
                    continue;
                }
                //判断障碍
                if(map[x][y]=='1' || map[x][y]=='G' || map[x][y]=='#'){
                    x = x - next[i][0];
                    y = y - next[i][1];
                    continue;
                }
                //写入队列
                if(map[x][y] == '.'){
                    map[x][y] = '1';
                    nodes[tail].x = x;
                    nodes[tail].y = y;
                    tail++;
                    judge(x,y);
                }
            }
            head++;
            x = nodes[head].x;
            y = nodes[head].y;
        }
    }

    public static void judge(int x2,int y2){
        int n = 0;
        while (x>0){
            x--;
            if(map[x][y] == 'G'){
                n++;
            }
            else if(map[x][y] == '#'){
                x = x2;
                y = y2;
                break;
            }
        }
        while (y>0){
            y--;
            if(map[x][y] == 'G'){
                n++;
            }
            else if(map[x][y] == '#'){
                x = x2;
                y = y2;
                break;
            }
        }
        while (x<12){
            x++;
            if(map[x][y] == 'G'){
                n++;
            }
            else if(map[x][y] == '#'){
                x = x2;
                y = y2;
                break;
            }
        }
        while (y<12){
            y++;
            if(map[x][y] == 'G'){
                n++;
            }
            else if(map[x][y] == '#'){
                x = x2;
                y = y2;
                break;
            }
        }
        if(n>max){
            max = n;
        }
    }
}

class Node_2{
    int x;
    int y;
}
